# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=26
    
    PROBLEM
    
    A unit fraction contains 1 in the numerator. The decimal representation
    of the unit fractions with denominators 2 to 10 are given:

    1/2	    = 	0.5
    1/3	    = 	0.(3)
    1/4	    = 	0.25
    1/5	    = 	0.2
    1/6	    = 	0.1(6)
    1/7	    = 	0.(142857)
    1/8	    = 	0.125
    1/9	    = 	0.(1)
    1/10	= 	0.1

    Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It
    can be seen that 1/7 has a 6-digit recurring cycle.

    Find the value of d < 1000 for which 1/d contains the longest recurring
    cycle in its decimal fraction part.

    
    NOTES
        
    
    REFERENCES
    
    
    PERFORMANCE
    time <function solution at 0x7f3d338217d0>: 0.398564 s
    
"""
#
# Import
#
import time


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    f = "value %s != expected %s"
    f = message != '' and f + " (%s)" or f + "%s"
    assert value == expected, f % (value, expected, message)


#
# Test Case / Solution
#
@timeit    
def test_case():
    expected = [
        (3, 3),
        (6, 6),
        (7, 142857),
        (9, 1)
    ]
    
    recurrents = []
    for n in range(2,11):
        recurring_cycle = get_recurring_cycle(n)
        if recurring_cycle:
            recurrents.append((n, recurring_cycle))
            
    assert_match(recurrents, expected)
    assert_match(7, sorted(expected, key=lambda t: len(str(t[1])))[-1][0])
    print "test case passed!"

@timeit
def solution():
    recurrents = []
    
    for n in range(2,1000):
        recurring_cycle = get_recurring_cycle(n)
        if recurring_cycle:
            recurrents.append((n, recurring_cycle))
            
    sort_key = lambda (n, cycle): len(str(cycle))
    sorted_recurrents = sorted(recurrents, key=sort_key, reverse=True)
    return sorted_recurrents[0]


#
# Solution Code
#
def get_recurring_cycle(n):
    """returns recurring cycle or None if none for 1 / n"""
    m = len(str(n))     # magnitude
    d = 10**m           # divisor (based on magnitude)
    
    rs = [1, d % n]     # remainders
    ds = [d / n]        # divisors
    
    while True:
        ds += [(rs[-1] * 10) / n]
        
        # non-repeater
        if rs[-1] == 0:
            return None
        
        # repeater
        elif rs[-1] in rs[:-1]:
            i = rs.index(rs[-1])
            return int(''.join([str(d) for d in ds[i:-1]]))
        
        # get next remainder
        else:
            rs += [(rs[-1] * 10) % n]



#
# Additional Tests
#



#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    